
% \section{Proposed Algorithm}

%In this section, 
Now we introduce our random walk assisted 
best-first search (RW-BFS) algorithm framework.  
% Heuristic evaluation in this is delayed

\begin{algorithm}[t] 
\caption{The RW-BFS Algorithm}
\label{bestfirst}
\LinesNumbered
% \SetAlgoLined 
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\Input{Initial state $s_{0}$} 

$open  \leftarrow  s_{0}$ \; 
\While{$open$ is not empty}{
	$s \leftarrow$ fetch($open$)\; 
	\If {$s$ is goal}
		{ \Return {\it solution found} \;}
	\If {$h(s) \le h^{*}$} 
		 { $ h^{*} \leftarrow h(s) $ \; }
	\If {$s$ is not a dead end} {
		$closed \leftarrow s $\;
		\ForEach {$ s_{i} \in $ successor($s$) } 
		{	evaluate $h(s_{i})$\;
			$open \leftarrow  (s_{i}, h(s_{i}) ) $  \;
		} % Foreach
	}	% end if
	\If { detect plateau } { 
    $open \leftarrow$~{\em random walk exploration} ($s$, $h^{*}$)\; 
  } 
} % end while	
\Return {\it no solution}
\end{algorithm}



\begin{algorithm}[h] 
\caption{Random Walk Exploration}
\label{findplat}
\LinesNumbered
% \SetAlgoLined 
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\Input{ a state $s$, the incumbent heuristic value $h^{*}$ } 

%$counter \leftarrow 0$ \;
%\For{ $i \leftarrow 0$ \KwTo ~limit }{
  $s' \leftarrow s$\; 
	%$trial \leftarrow 0$ \;
	%\For { $trial \leftarrow 0 \cdots$~cuttoff } {
		%$ j \leftarrow 0$ \;
		\For {  $j \leftarrow 1$ \KwTo ~t } {
      %$s' \leftarrow walk(s', l_{i}, n_{i})$ \;
      			decide parameters $l$, $n$ \;
			$s' \leftarrow walk(s', l, n)$ \;

      \If{$s'$ is dead-end}{
        $s' \leftarrow s$\;
      }
      \ElseIf {$ h(s') <  h^{*}$ } { \Return $s'$\; }
      %\If {$ h(s') \le h_{best}$ } { \Return $s'$ \; }
%			 \leftarrow $ heuristic of $s'$ \;
%			$w \leftarrow w + 1$ \;
		}	% end for
%		$s \leftarrow $ best of ($h(s')$) \;
%	}	% end while
%}% end while
%\Return;
\end{algorithm}


%%%%%%%%% Random walk
\begin{algorithm}[h] 
\caption{Walk}
\label{walk}
\LinesNumbered
% \SetAlgoLined 
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\Input{ a state $s$, the parameter $l$, the parameter $n$ }
$c \leftarrow 0$ \;
$s' \leftarrow s$ \;
\For{$ c \leftarrow 1$ \KwTo $n$}{
	\For { $j \leftarrow 1$ \KwTo $l$ } {
		$o \leftarrow $ a random applicable action in $s'$ \;
		$s' \leftarrow apply(s', o)$ \;
	%	$ j  \leftarrow  j+1$ \; 
	}
	\If {$ h(s') < h_{min} $ } 
	{
		$s_{min} \leftarrow s'$ \;
	}
}% end while
\Return $s_{min}$ \;
\end{algorithm}


Our proposed RW-BFS algorithm is presented in Figure~\ref{bestfirst}. 
It is a variant of a standard best-first search procedure. 
In addition to the original best-first search algorithm, 
RW-BFS adds a {\em detect plateau} check after expanding a new state 
(Line 13 in Algorithm~\ref{bestfirst}). If a plateau is detected, 
the {\em random walk exploration} 
procedure will be called to explore the search space in order to find a state that can reduce $h^{*}$. Meanwhile, $h^{*}$, 
the incumbent heuristic value, is updated whenever 
a state with a smaller heuristic value is found (Line 6-7 in 
Algorithm~\ref{bestfirst}). 

Algorithm~\ref{findplat} presents the {\em random walk exploration} procedure. 
It essentially adopts the Monte-Carlo exploration algorithm proposed in~\cite{Nakhost09}. 
Given a state $s$ and $h^{*}$, it explores $s$'s neighbors 
using a sequence of ($t$) random walks. A state is returned 
if its heuristic function value is lower than $h^{*}$ (Line 7-8  in Algorithm~\ref{findplat}).
 
At each iteration, it initializes parameters $l, n$ that are used in {\em walk}. Then, 
it invokes {\em walk} to visit a new state $s'$ (Line 4). 
If $s'$ is a dead-end, this algorithm will restart from the input state $s$ (Line 5-6).
If $s'$ has even smaller heuristic value than $h^{*}$, this state 
will be returned to Algorithm~\ref{bestfirst}. Otherwise, 
$s'$ will be used as a new starting state for the next walk. 
The number of walks is bounded by $t$, so that 
this algorithm always returns in finite time, 
whether a better state $s'$ is found or not. 

Algorithm~\ref{walk} gives a detailed view of the {\em walk }
procedure. Given a starting state $s$ and two 
parameters $l$ and $n$, Algorithm~\ref{walk} will try  $n$ paths, 
where each path is a random sequence of $l$ actions.
The procedure will return the best ending state among the $n$ paths. 
Note that for any path yielded by Algorithm~\ref{walk}, heuristic functions 
are evaluated only at the end 
of the $l$ actions (Line 7). 

\nop{
to find the best state $s_{min}$ that has the least 
heuristic value at the end of the path. 
}
\nop{
Note that both $l$
and $n$ are assigned in Algorithm~ref{findplat}. 
}

\noindent {\bf Plateau Detection.} The performance of our algorithm also 
depends on the performance of the {\em  detect plateau}
procedure used in Algorithm~\ref{bestfirst}. 

This plateau detection test can neither be 
too sensitive nor too unresponsive. 
If it is too sensitive, the {\em random walk exploration} 
procedure will be invoked frequently and the progress of the best-first search 
may be hindered by constant interruption. On the other hand, if this detection 
is unresponsive, our designed random walks cannot help the best-first search
as desired. Therefore, a balanced plateau detection mechanism is 
needed. In our proposed algorithm, the following two 
conditions are used to decide if the best-first search is currently 
on a plateau. 

\begin{itemize}
\item The value of $h^{*}$ is not reduced for $m$ consecutive states; or

\item The moving average of the heuristic values of $w$ recent states is higher than $h^{*} + \delta$
where $\delta$ is a threshold that reduces gradually during search. 

% If the moving average of all states visiting in the open list is significantly higher than the best
% value we have visited in the open list, we consider it is a plateau. 

\end{itemize}

\nop{ 
 % we can not see states that are not yet visited, 
}
% The second condition is used where BFS is exploring a large amount of nodes to climb over a 
% local maximal, RW can be used to assist it. 
